2025-10-22 Recursion 2

Turing Completeness of PCF

PCF is Turing complete because all partial recursive functions can be defined in PCF. Partial recursive functions are used to prove Turing completeness because they themselves are Turing complete, so if you can embed them in your language, your language is Turing complete.

Sequentiality of PCF

The parallel OR function cannot be expressed in PCF so it cannot perform parallel operations.